package com.dyz.leetcode;

import java.util.Arrays;

public class CoinChange322 {
    //暴力求解， 递归，全排列 时间超时
    public int coinChange(int[] coins, int amount) {
        if(amount==0){return 0;}
        if(coins==null||coins.length==0){return -1;}

        return helper(coins, amount);
    }
    private int helper(int[] coins, int amount){
        //递归终止
        if (amount==0){return 0;}
        int res = Integer.MAX_VALUE;
        for (int coin:coins){
            if (amount >= coin) {
                int tres = helper(coins, amount-coin);
                if (tres == -1){
                    continue;
                }else {
                    res = Math.min(res, tres+1);
                }
            }
        }
        if(res == Integer.MAX_VALUE){return -1;}
        return res;
    }

    //动态求解， 递归，全排列 时间超时--》解决，动态，以空间换时间
    int[] dp;
    public int coinChange2(int[] coins, int amount) {
        if(amount==0){return 0;}
        if(coins==null||coins.length==0){return -1;}
        //定义容器
        dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        //状态转移 dp[i] = Math.min(dp[i-coin]+1, dp[i])
        for (int curAmount=1; curAmount<=amount; curAmount++){
            for(int coin:coins){
                int leftAmount = curAmount -coin;
                if(leftAmount<0 || dp[leftAmount]==Integer.MAX_VALUE){continue;}
                dp[curAmount] = Math.min(dp[leftAmount]+1, dp[curAmount]);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }

}
